package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-6-24
 * Time: 上午9:08
 * To change this template use File | Settings | File Templates.
 */
public class Sort_Colors {//使用O（n）空间。其实可以实现O（1）空间。
    public void sortColors(int[] A) {
        int begin = 0,end = A.length-1;
        int[] B = new int[A.length];
        for(int i=0;i<B.length;i++)
            B[i]=1;
        for(int i=0;i<A.length;i++){
            if(A[i]==0){
                B[begin]=0;
                begin++;
            }
            else if(A[i]==2){
                B[end]=2;
                end--;
            }
        }
        for(int i=0;i<A.length;i++)
            A[i] = B[i];
    }
    public static void main(String[] args){
        int[] A = {0,2,0,0,1,2,1,1,2,2,1,2,2};
        Sort_Colors sort_colors = new Sort_Colors();
        sort_colors.sortColors(A);
        for(int i=0;i<A.length;i++){
            System.out.print(" "+A[i]);
        }
    }
}
